#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <algorithm>
#include <cstdlib>
#include <ctime>

using namespace std;

// 生成随机指令序列
vector<int> generateInstructionSequence(int numPages, int totalInstructions) {
    vector<int> sequence;
    srand(time(0));
    for (int i = 0; i < totalInstructions; ++i) {
        sequence.push_back(rand() % numPages);
    }
    return sequence;
}

// FIFO 页面置换算法
double fifoPageReplacement(const vector<int>& sequence, int frameSize) {
    queue<int> memory;
    unordered_map<int, bool> inMemory;
    int diseffect = 0;
    for (int page : sequence) {
        if (inMemory[page]) continue;
        if (memory.size() == frameSize) {
            int oldestPage = memory.front();
            memory.pop();
            inMemory[oldestPage] = false;
        }
        memory.push(page);
        inMemory[page] = true;
        diseffect++;
    }
    return 1.0 - static_cast<double>(diseaseffect) / sequence.size();
}

// LRU 页面置换算法
double lruPageReplacement(const vector<int>& sequence, int frameSize) {
    list<int> memory;
    unordered_map<int, list<int>::iterator> posMap;
    int diseffect = 0;
    for (int page : sequence) {
        if (posMap.find(page) != posMap.end()) {
            memory.erase(posMap[page]);
        }
        else {
            if (memory.size() == frameSize) {
                int lruPage = memory.back();
                memory.pop_back();
                posMap.erase(lruPage);
            }
            diseffect++;
        }
        memory.push_front(page);
        posMap[page] = memory.begin();
    }
    return 1.0 - static_cast<double>(diseffect) / sequence.size();
}

// OPT 页面置换算法（假设未来知道所有页面请求）
double optPageReplacement(const vector<int>& sequence, int frameSize) {
    vector<int> future(sequence.size(), -1);
    unordered_map<int, vector<int>> pageIndices;
    for (int i = 0; i < sequence.size(); ++i) {
        pageIndices[sequence[i]].push_back(i);
    }
    for (auto& entry : pageIndices) {
        reverse(entry.second.begin(), entry.second.end());
    }

    set<int> memory;
    int diseffect = 0;
    for (int i = 0; i < sequence.size(); ++i) {
        int page = sequence[i];
        if (memory.find(page) != memory.end()) continue;
        if (memory.size() == frameSize) {
            int farthestPage = -1;
            int farthestIndex = -1;
            for (int p : memory) {
                while (!pageIndices[p].empty() && pageIndices[p].back() <= i) {
                    pageIndices[p].pop_back();
                }
                if (pageIndices[p].empty()) {
                    farthestPage = p;
                    break;
                }
                if (pageIndices[p].back() > farthestIndex) {
                    farthestIndex = pageIndices[p].back();
                    farthestPage = p;
                }
            }
            memory.erase(farthestPage);
        }
        memory.insert(page);
        diseffect++;
    }
    return 1.0 - static_cast<double>(diseffect) / sequence.size();
}

int main() {
    int numPages, totalInstructions, frameSize;
    cout << "请输入页面总数: ";
    cin >> numPages;
    cout << "请输入总指令数: ";
    cin >> totalInstructions;
    cout << "请输入内存物理块数量: ";
    cin >> frameSize;

    vector<int> sequence = generateInstructionSequence(numPages, totalInstructions);

    double fifoHitRate = fifoPageReplacement(sequence, frameSize);
    double lruHitRate = lruPageReplacement(sequence, frameSize);
    double optHitRate = optPageReplacement(sequence, frameSize);

    cout << "FIFO 命中率: " << fifoHitRate * 100 << "%" << endl;
    cout << "LRU 命中率: " << lruHitRate * 100 << "%" << endl;
    cout << "OPT 命中率: " << optHitRate * 100 << "%" << endl;

    return 0;
}



